package com.qxy.hot3;
import com.google.errorprone.annotations.Var;
import com.qxy.hot1.ListNode;

import javax.xml.transform.SourceLocator;
import java.util.ArrayList;
import java.util.List;

/**
 * @author : 戚欣扬
 * @description : 链表排序
 */
public class Solution {
    private List<List<String>> result =  new ArrayList<>();
    private List<String> path = new ArrayList<>();
    private int num;
    public List<List<String>> solveNQueens(int n) {
        num = n;
        solveNQueensHelper(1);
        return result;
    }
    private void solveNQueensHelper(int depth){
        if(path.size() == num){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ; i<num;i++){
            //合法位置的话就构造当前层的皇后String输出
            if(isValid(depth,i)){
                StringBuilder tmp = new StringBuilder("");
                for(int j = 0 ;j <num;j++){
                    tmp.append('.');
                }
                tmp.setCharAt(i,'Q');
                path.add(tmp.toString());
                solveNQueensHelper(depth+1);
                path.remove(path.size()-1);
            }
            continue;
        }
        return;
    }
    //row = depth(init=1) col(init=0)
    private boolean isValid(int row,int col){
        if(row-1==0) return true;
        for(int i = row-2;i>-1;i--){
            StringBuilder tmp = new StringBuilder(path.get(i));
            //col列为皇后，失败,row不考虑
            if(tmp.charAt(col) == 'Q') return false;
            //对角线
            int inValidCol1 = row-(i+1);
            int inValidCol2 = (i+1)-row;
            if(inValidCol1>-1 && tmp.charAt(inValidCol1)=='Q') return false;
            if(inValidCol2>-1 && tmp.charAt(inValidCol2)=='Q') return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solveNQueens(4);
    }
}


